//== SAGITTARIUS ============================================================================

//== BEGINNING OF CODE ===============================================================

#include "sagittarius/core/SagittariusCore.h"
#include "sagittarius/patterns/radixtree.h"
#include "sagittarius/io/io.h"
#include <malloc.h>
#include <string.h>

#if SAGITTARIUS_COMPILER == SAGITTARIUS_COMPILER_GNUC || SAGITTARIUS_COMPILER == SAGITTARIUS_COMPILER_MINGW
inline
#endif
void grow_radix_node(radixnode* n) {
    //sema must be locked
    radixnode** tmp;
    size_t sz=n->sz*RADIXTREE_DEFAULT_NEDGES;
    tmp = malloc(sz*sizeof(radixnode*)); //TODO: use sgmalloc
    memcpy(tmp, n->edges, n->sz);
    free(n->edges);
    n->edges = tmp;
    n->sz = sz;
}

radixnode* create_radix_node(int terminal, constLexBuf label) {
    radixnode* n;
    n = (radixnode*)malloc(sizeof(radixnode)); //TODO: use sgmalloc
    n->sz = RADIXTREE_DEFAULT_NEDGES;
    n->edges = (radixnode**)malloc(n->sz*sizeof(radixnode*)); //TODO: use sgmalloc
    memset(n->edges, 0, n->sz*sizeof(radixnode*));
    n->nedges = 0;
    n->terminal = terminal;
    
    if(label) {
        n->labellen = LX_BUFFER_LEN(label);
        n->label = LX_CREATE_BUFFER(n->labellen);
        LX_COPY(n->label, label, n->labellen);
        //n->label[n->labellen-1] = '\0'; //insert null-terminating character
    } else {
        n->label = NULL;
        n->labellen = 0;
    }
    
    n->p = NULL;
    
    return n;
}

radixnode* create_radix_root() {
    return create_radix_node(0, NULL);
}

//labeled
radixnode* create_radix_nodel(constLexBuf label) {
    radixnode* new;
    
    new = create_radix_node(1, label);
    return new;
}

void destroy_radix_node(radixnode* n) {
    size_t i;
    //label
    if(n->label)
        LX_FREE_BUFFER(n->label);
    //edges
    AT(n->edges); //FIXME: I don't think this is appropriate
    for(i=0; i<n->nedges; ++i)
        destroy_radix_node(n->edges[i]);
    free(n->edges);
    
    //NOTE: we would need to call an actual destructor here to make this work
    //if(n->p)
        //free(n->p); //free data
    
    free(n);
}

//links existing
void radix_node_link_edge(radixnode* n, radixnode* l) {
    if(n->nedges >= n->sz)
        grow_radix_node(n);
    n->edges[n->nedges++] = l;
}

//adds new
void radix_node_add_edge(radixnode* n, constLexBuf label, void* p) {
    radixnode* new;
    
    new = create_radix_nodel(label);
    radix_node_link_edge(n, new);
    new->p = p;
}

//create with children
radixnode* create_radix_nodel_w2children(constLexBuf label, radixnode* c1, radixnode* c2) {
    radixnode* new = create_radix_nodel(label);
    new->terminal = 0;
    radix_node_link_edge(new, c1);
    radix_node_link_edge(new, c2);
    return new;
}

//create with child
radixnode* create_radix_nodel_wchild(constLexBuf label, radixnode* c, int terminal) {
    radixnode* new = create_radix_nodel(label);
    new->terminal = terminal;
    radix_node_link_edge(new, c);
    return new;
}

size_t radix_compare_prefix(constLexBuf str, constLexBuf prefix) {
    /*SG_WRITE(2, "radix_compare_prefix: str = ");
    LX_WRITE_BUF(2, str);
    SG_WRITE(2, ", prefix = ");
    LX_WRITE_BUF(2, prefix);
    SG_WRITE(2, "\n");*/
    size_t i=0;
    constLexBuf s=str;
    //NOTE: prefixes MUST be terminated with '\0'
    while(1) {
        /*SG_WRITE(2, "*s = ");
        //LX_WRITE_BUFL(2, s, 1);
        LX_ALPHA_WRITEINT(2, *s);
        SG_WRITE(2, "\n");
        SG_WRITE(2, "*prefix = ");
        //LX_WRITE_BUFL(2, prefix, 1);
        LX_ALPHA_WRITEINT(2, *prefix);
        SG_WRITE(2, "\n");*/
        if((!LX_CMPALPHA_EQ(*s, *prefix)) || LX_CMPALPHA_EQ_SPC(*prefix, '\0')) {
            /*SG_WRITE(2, "BADBRANCH\n*s = ");
            //LX_WRITE_BUFL(2, s, 1);
            LX_ALPHA_WRITEINT(2, *s);
            SG_WRITE(2, "\n");
            SG_WRITE(2, "*prefix = ");
            //LX_WRITE_BUFL(2, prefix, 1);
            LX_ALPHA_WRITEINT(2, *prefix);
            SG_WRITE(2, "\n");
            SG_WRITE(2, "Value of LX_CMPALPHA_EQ(*s, *prefix): ");
            sg_writeUInt64(2, LX_CMPALPHA_EQ(*s, *prefix));
            SG_WRITE(2, "\nLX_CMPALPHA_EQ_SPC(*prefix, '\0'): ");
            sg_writeUInt64(2, LX_CMPALPHA_EQ_SPC(*prefix, '\0'));
            SG_WRITE(2, "\n");*/
            return i;
        }
        ++s;
        ++prefix;
        ++i;
    }
}

int radix_is_terminal(radixnode* n) {
    radixnode** i=n->edges;
    
    for(; (*i)!=NULL; ++i) {
        if((*i)->labellen == 0)
            return 1;
    }
    return 0;
}

radixnode* radix_get(radixnode* n, constLexBuf label) {
    size_t      v;
    size_t      buflen = LX_BUFFER_LEN(label); //includes null char
    radixnode** i=n->edges;
    
    for(; (*i)!=NULL; ++i) {
        v = radix_compare_prefix(label, (*i)->label);
        /*SG_WRITE(2, "v = ");
        sg_writeUInt64(2, v);
        SG_WRITE(2, "\n");*/
        if(v == 0)
            continue;
        if(v+1 == buflen) {
            if(v+1 == (*i)->labellen && (*i)->terminal)
                return *i;
            else
                return NULL;
        } else if(v+1 == (*i)->labellen) {
            return radix_get(*i, label+v);
        } else {
            return NULL;
        }
    }
    return NULL;
}

//shrinks off end
void radix_shrink_label(radixnode* n, size_t len) {
    LexBuf tmp;
    
    tmp = LX_CREATE_BUFFER(len);
    LX_COPY(tmp, n->label, len-1);
    LX_ALPHA_SET_SPC(tmp[len-1], '\0');
    LX_FREE_BUFFER(n->label);
    
    n->labellen = len;
    n->label = tmp;
}

//chops off front
void radix_chop_label(radixnode* n, size_t k) {
    size_t len = n->labellen - k;
    LexBuf tmp;
    
    tmp = LX_CREATE_BUFFER(len);
    LX_COPY(tmp, n->label+k, len-1);
    LX_ALPHA_SET_SPC(tmp[len-1], '\0');
    LX_FREE_BUFFER(n->label);
    
    n->labellen = len;
    n->label = tmp;
}

int radix_search_and_add(radixnode* n, constLexBuf str, void* p) {
    size_t      buflen = LX_BUFFER_LEN(str); //includes null char
    size_t      v;
    radixnode** i=n->edges;
    LXAlphaType tmp;
    
    /*SG_WRITE(2, "radix_search_and_add str = ");
    sg_writeUStr(2, str);
    SG_WRITE(2, "\n");*/
    
    for(; (*i)!=NULL; ++i) {
        v = radix_compare_prefix(str, (*i)->label);
        if(v == 0)
            continue;
        if(v+1 == buflen) {
            if(v+1 == (*i)->labellen)
                return 1; //already exists
            
            //full match on label
            //SG_WRITE(2, "full match on label\n");
            //truncate and add outgoing
            LX_FORCE_INIT(tmp);
            LX_ALPHA_SET(tmp, (*i)->label[v]); //it would be nice to inline an asm swap
            LX_ALPHA_SET_SPC((*i)->label[v], '\0');
            (*i) = create_radix_nodel_wchild((*i)->label, *i, 1);
            LX_ALPHA_SET((*i)->edges[0]->label[v], tmp);
            LX_ALPHA_CLEAR(tmp);
            radix_chop_label((*i)->edges[0], v);
            
            (*i)->p = p; //add data
            return 0;
        } else if(v+1 == (*i)->labellen) {
            //full match on node
            //SG_WRITE(2, "full match on node\n");
            if((*i)->terminal) { //FIXME: Bug? Why stop at terminal node?
                radix_node_add_edge(*i, str+v, p);
                return 0;
            } else
                //try to get more matches
                return radix_search_and_add(*i, str+v, p);
        } else {
            //partial match for both
            /*SG_WRITE(2, "double partial match on node ");
            LX_WRITE_BUF(2, (*i)->label);
            SG_WRITE(2, "\n");*/
            LX_FORCE_INIT(tmp);
            LX_ALPHA_SET(tmp, (*i)->label[v]); //it would be nice to inline an asm swap
            LX_ALPHA_SET_SPC((*i)->label[v], '\0');
            (*i) = create_radix_nodel_w2children((*i)->label, *i, create_radix_nodel(str+v));
            LX_ALPHA_SET((*i)->edges[0]->label[v], tmp);
            LX_ALPHA_CLEAR(tmp);
            radix_chop_label((*i)->edges[0], v);
            
            (*i)->edges[1]->p = p; //data
            return 0;
        }
    }
    radix_node_add_edge(n, str, p);
    return 0;
}

void radix_print_ind(const int fd, const int ind) {
    int i=0;
    for(; i<ind; ++i)
        SG_WRITE(fd, " ");
}

void dump_radix_node(const int fd, radixnode* n, int ind) {
    radixnode** i=n->edges;
    
    radix_print_ind(fd, ind);
    SG_WRITE(fd, "--Radix node\n");
    radix_print_ind(fd, ind);
    if(n->label) {
    SG_WRITE(fd, "  Label \"");
        LX_WRITE_BUF(fd, n->label);
        SG_WRITE(fd, "\"\n");
    } else
        SG_WRITE(fd, "  No label\n");
    
    //dump children
    for(; (*i)!=NULL; ++i)
        dump_radix_node(fd, *i, ind+2);
}